#include <bits/stdc++.h>
using namespace std;

/*
3403. 从盒子中找出字典序最大的字符串 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：

word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
所有分割出的字符串都会被放入一个盒子中。
在所有回合结束后，找出盒子中 字典序最大的 字符串。

 

示例 1：

输入: word = "dbca", numFriends = 2

输出: "dbc"

解释: 

所有可能的分割方式为：

"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。
示例 2：

输入: word = "gggg", numFriends = 4

输出: "g"

解释: 

唯一可能的分割方式为："g", "g", "g", 和 "g"。

 

提示:

1 <= word.length <= 5 * 103
word 仅由小写英文字母组成。
1 <= numFriends <= word.length
*/

// 法一 枚举
class Solution {
public:
    // 函数answerString用于找出将字符串word分割成numFriends个非空字符串后，字典序最大的那个字符串
    string answerString(string word, int numFriends) {
        // 如果只需要分割成1个字符串，那么直接返回整个word
        if (numFriends == 1) {
            return word;
        }
        int n = word.size();
        // 用于存储最终结果，即字典序最大的子串
        string res;
        // 遍历字符串word的每个位置i
        for (int i = 0; i < n; i++) {
            // 这里通过min函数来确定截取子串的长度。
            // n - numFriends + 1确保剩余部分至少还能分成numFriends - 1个非空字符串
            // n - i 确保不会截取超出字符串末尾的部分
            res = max(res, word.substr(i, min(n - numFriends + 1, n - i)));
            // 将当前截取的子串与res比较，取字典序较大的更新res
        }
        return res;
    }
};

// 法二  双指针
class Solution {
public:
    // answerString 函数用于在将字符串 s 分割成 k 个非空字符串的所有可能结果中，找出字典序最大的字符串
    string answerString(string s, int k) {
        // 如果只需要分割成1个字符串，直接返回原始字符串 s
        if (k == 1) {
            return s;
        }
        int n = s.size();
        // i 用于标记当前考虑的子串起始位置，初始化为 0
        int i = 0;
        // j 用于标记下一个可能的子串起始位置，初始化为 1
        int j = 1;

        // 遍历字符串，寻找字典序最大的子串起始位置
        while (j < n) {
            // k 用于记录两个子串从起始位置开始相同字符的长度
            int k = 0;
            // 比较从 i 和 j 开始的子串，找到第一个不同字符的位置
            while (j + k < n && s[i + k] == s[j + k]) {
                k++;
            }
            // 如果 j + k 还在字符串范围内，且 s[i + k] 小于 s[j + k]
            // 说明从 j 开始的子串字典序更大，更新 i 和 j
            if (j + k < n && s[i + k] < s[j + k]) {
                int t = i;
                i = j;
                // j 更新为 j + 1 和 t + k + 1 中的较大值
                j = max(j + 1, t + k + 1);
            }
            // 否则，说明从 i 开始的子串字典序不小于从 j 开始的子串
            // j 直接移动到当前比较结束位置的下一个位置
            else {
                j += k + 1;
            }
        }
        // 返回从 i 开始的子串，长度为 n - max(k - 1, i)
        return s.substr(i, n - max(k - 1, i));
    }
};
